import java.io.IOException;
import java.util.*;
import static java.lang.Thread.sleep;
import java.util.Calendar;

class Node{ //结点类

    int number; //该点编号
    int length; //到该点距离

    public Node(int number, int length) {
        this.number = number;
        this.length = length;
    }
}
class dijkstra {    //存放各种算法

    static LinkedHashMap<Integer, Integer> disMap = new LinkedHashMap<>();  //按远近存储给定起点到各点的距离
    static ArrayList<ArrayList<Integer>> Path = new ArrayList<>();  //存储给定起点到各点的路径

    static int[][] edge_array = new int[Navigation.m][3];   //三种搜索方案对应的边集
    static int[][] edge_array2 = new int[Navigation.m][3];
    static int[][] edge_array3 = new int[Navigation.m][3];

    static boolean pauseFlag;   //用于通过子线程控制模拟导航是否继续
    static boolean stopFlag;    //用于通过子线程控制多途经点模拟导航是否继续

    static{
        int cnt = 0;

        for(myEdge a:Input.edges) { //最短路
            edge_array[cnt][0] = a.Start;
            edge_array[cnt][1] = a.End;
            edge_array[cnt++][2] = a.Weight;
        }

        cnt = 0;

        for(myEdge a:Input.edges) { //最短时间
            edge_array2[cnt][0] = a.Start;
            edge_array2[cnt][1] = a.End;
            edge_array2[cnt++][2] = a.Weight * a.Volume;
        }

        cnt = 0;

        for(myEdge a:Input.edges) { //允许自行车下的最短路
            if(a.Bicycle){
                edge_array3[cnt][0] = a.Start;
                edge_array3[cnt][1] = a.End;
                edge_array3[cnt++][2] = a.Weight;
            }
        }
    }

    public static void Dijkstra(int start) throws IOException { //使用邻接表与优先队列实现的dijkstra算法

        Scanner in = new Scanner(System.in);
        int INF = 100000000;
        boolean[] vis = new boolean[Navigation.n+1];    //是否造访过该点
        int[] dis = new int[Navigation.n+1];            //起点到每个点的距离
        int[] No = new int[Navigation.n+1];             //每个点的编号
        int temp;   //排序使用的中间变量

        ArrayList<ArrayList<Node>> arrs = new ArrayList<>();
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<Integer>((o1, o2) -> dis[o1]-dis[o2]);   //构造优先队列,使用dis排序

        for(int i = 0; i <= Navigation.n; i++) arrs.add(new ArrayList<>()); //初始化ArrayList
        for(int i = 0; i <= Navigation.n; i++) Path.add(new ArrayList<>());

        while (Navigation.mode < 0 || Navigation.mode > 2){

            fileOutput.Cacheln(true, "输入导航策略：(0为最短路，1为最短时间，2为自行车导航)");
            Navigation.mode = in.nextInt();
            fileOutput.Cacheln(false, Navigation.mode);

            if (Navigation.mode < 0 || Navigation.mode > 2)
                fileOutput.Cacheln(true, "mode输入错误！");
        }

        if (Navigation.mode == 0)   //将不同的方案存入
            for (int[] time:edge_array)
                arrs.get(time[0]).add(new Node(time[1],time[2]));
        else if (Navigation.mode == 1)
            for (int[] time:edge_array2)
                arrs.get(time[0]).add(new Node(time[1],time[2]));
        else if (Navigation.mode == 2)
            for (int[] time:edge_array3)
                arrs.get(time[0]).add(new Node(time[1],time[2]));


        Arrays.fill(dis,INF);   //初始化dis数组
        dis[start] = 0;

        for(ArrayList a:Path) { //初始化路径
            a.clear();
            a.add(start);
        }

        priorityQueue.offer(start); //添加起点

        while(!priorityQueue.isEmpty()){
            Integer curr = priorityQueue.poll();  //取队首并出队列
            if(vis[curr]) continue; //若造访过则继续

            vis[curr] = true;   //设定为造访过
            Path.get(curr).add(curr);   //路径添加该点

            for(Node node:arrs.get(curr)){  //对剩下的每个点更新数据
                if(vis[node.number]) continue;

                if (dis[curr] + node.length < dis[node.number]){
                    dis[node.number] = dis[curr] + node.length;

                    if (curr != start) {    //若不是起点,将到该点的最短路径直接覆盖掉该点的路径

                        Path.get(node.number).clear();
                        for(int t:Path.get(curr))
                            Path.get(node.number).add(t);
                    }
                }

                priorityQueue.offer(node.number);   //凡是更新过的点均入队
            }
        }

        for (int i = 0; i < Navigation.n; i++) No[i] = i;   //初始化序号数组

        for (int i = 0; i < Navigation.n - 1; i++)  //对dis进行排序
            for (int j = i + 1; j < Navigation.n; j++)
                if (dis[i] > dis[j]){
                    temp = dis[i];
                    dis[i] = dis[j];
                    dis[j] = temp;

                    temp = No[i];
                    No[i] = No[j];
                    No[j] = temp;
                }

        disMap.clear(); //初始化disMap,并把排序后的结果填入disMap中,使用HashMap方便查找
        for (int i = 0; i < Navigation.n; i++) disMap.put(No[i], dis[i]);
    }

    public static void Simulation(int start, int end) throws IOException {  //模拟导航

        fileOutput.Cacheln(true, "\n开始模拟导航");
        if (start == end) {
            fileOutput.Cacheln(true, "原地待命!");
            Navigation.curBuilding = Input.buildings.get(start);
        }
        else {
            fileOutput.Cacheln(true, "输入每秒钟行走的米数");

            Scanner in = new Scanner(System.in);

            int cur = 0;        //当前共到过几个点
            int addLength;      //这一步增加的长度
            int curLength = 0;  //在当前路上走的长度
            int stepLength = in.nextInt();  //步长
            int curStart = start;   //当前边的起点,初始化为路径起点
            int curEnd = dijkstra.Path.get(end).get(cur + 1);   //当前边的终点,初始化为路径的第二个点
            pauseFlag = false;  //初始化暂停标志为不暂停

            fileOutput.Cacheln(false, stepLength);

            simulationPause pp = new simulationPause();
            Thread pause = new Thread(pp);  //创建子线程

            pause.start();  //启动子线程
            stopFlag = false;
            while (curStart != end) {

                try {

                    sleep(1000); //1000ms输出一次信息
                    if (pauseFlag) {    //若子线程监听到键盘事件(输入0)
                        fileOutput.Cacheln(true, "模拟暂停，当前位于" + Navigation.curBuilding.Building_Name);
                        stopFlag = true;
                        break;
                    }

                    if ((Search.FindPath(curStart, curEnd).Weight - curLength) > stepLength) //判断下一步长度,若小于步长则直接走到终点
                        addLength = stepLength;
                    else addLength = Search.FindPath(curStart, curEnd).Weight - curLength;

                    curLength += addLength; //模拟行走

                    /*判断当前位置离起点和终点谁更近,离谁近则近似为在建筑物附近,作为当前地址使用*/
                    if (curLength < Search.FindPath(curStart, curEnd).Weight / 2)
                        Navigation.curBuilding = Input.buildings.get(curStart);
                    else Navigation.curBuilding = Input.buildings.get(curEnd);

                    fileOutput.Cache("\n向" + Input.directionMap.get(Search.FindPath(curStart, curEnd).Direction) + "走" + addLength + "m");  //输出信息

                } catch (InterruptedException ex) {
                    Thread.currentThread().interrupt();
                }

                if (curLength == Search.FindPath(curStart, curEnd).Weight) { //当前已走到该边的尽头

                    fileOutput.Cache(" 到达" + Input.buildings.get(curEnd).Building_Name);    //输出信息

                    curLength = 0;  //当前长度重新定义为0
                    curStart = curEnd;  //下一个起点为上一个终点
                    cur++;  //又多走了一个点

                    if (curEnd != end) curEnd = dijkstra.Path.get(end).get(cur + 1); //若模拟未结束,当前终点设为下一个点
                }
            }
            pause.stop();   //未监听到键盘时间则结束进程(实际上不能结束,这是一个目前还解决不了的问题)
        }
    }

    public static void outPutPath(int end) throws IOException { //输出路径

        myEdge tempPath;    //用来存放当前要输出的边

        if (Navigation.mode != 1) fileOutput.Cacheln(true, "\n总距离为" + dijkstra.disMap.get(end) + "m");   //输出总距离

        fileOutput.Cacheln(true, "Path: ");
        if (dijkstra.disMap.get(end) == 0) fileOutput.Cacheln(true, "原地不动！"); //原地未动
        else for (int i = 0; i < dijkstra.Path.get(end).size() - 1; i++) { //否则输出路径

            tempPath = Search.FindPath(dijkstra.Path.get(end).get(i), dijkstra.Path.get(end).get(i + 1));
            fileOutput.Cacheln(true, "向" + Input.directionMap.get(tempPath.Direction) + "走" + tempPath.Weight + "m" + "到达" + Input.buildings.get(dijkstra.Path.get(end).get(i + 1)).Building_Name);
        }
    }

    public static void TP(int start, int flag, int end) throws IOException {    //跨校区导航,(flag == 0)为沙河->本部,否则反之

        Scanner in = new Scanner(System.in);

        fileOutput.Cacheln(true, "\n检测到跨校区，0公交，1校车");

        Calendar c = Calendar.getInstance();//可以对每个时间域单独修改

        fileOutput.Cacheln(true, "现在的时间为" + c.get(Calendar.HOUR_OF_DAY) + ":" + c.get(Calendar.MINUTE) + ":" + c.get(Calendar.SECOND));
        //int seconds = c.get(Calendar.HOUR_OF_DAY) * 3600 + c.get(Calendar.MINUTE) * 60 + c.get(Calendar.SECOND);  //实时判断
        int seconds = 39600;    //固定为11:00,根据需求取消屏蔽

        for (ArrayList<Integer> a:Input.timeTable)  //寻找下一趟校车,只要时间在当前时间之后即可

            if ((a.get(0) * 3600 + a.get(1) * 600) >= seconds){

                fileOutput.Cacheln(true, "下一班校车时间为" + a.get(0) + ":" + a.get(1) + "0");
                seconds = (a.get(0) * 3600 + a.get(1) * 600) - seconds; //秒变为差值,用来控制等校车的时长
                break;
            }

        int car = in.nextInt(); //车辆类型
        int waits, waitr;   //等车时长,车辆运行时长
        fileOutput.Cacheln(false, car);

        if (car == 0) { //公交: 等10秒,运行10秒

            waits = 10;
            waitr = 10;

            if (flag == 0) {
                dijkstra.outPutPath(26);    //沙河公交站
                dijkstra.Simulation(start, 26);
            }
            else {
                dijkstra.outPutPath(42);    //本部公交站
                dijkstra.Simulation(start, 42);
            }
        }
        else {  //校车: 等待时间不定,1秒对应10分钟,运行6秒

            waits = seconds / 600;
            waitr = 6;

            if (flag == 0) {
                dijkstra.outPutPath(33);    //沙河校车点
                dijkstra.Simulation(start, 33);
            }
            else {
                dijkstra.outPutPath(43);    //本部校车点
                dijkstra.Simulation(start, 43);
            }
        }

        fileOutput.Cache("\n等车中");

        for (int i = 1; i <= waits; i++)    //每隔1sec输出一个点
            try {
                sleep(1000);
                fileOutput.Cache(". ");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

        fileOutput.Cache("\n上车，车辆运行中");

        for (int i = 1; i <= waitr; i++)
            try {
                sleep(1000);
                fileOutput.Cache(". ");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

        System.out.println("\n");

        if (car == 0){  //按不同交通方式找到不同起点导航

            if (flag == 0) dijkstra.Dijkstra(42);
            else dijkstra.Dijkstra(26);
        }
        else{

            if (flag == 0) dijkstra.Dijkstra(43);
            else dijkstra.Dijkstra(33);
        }

        dijkstra.outPutPath(end);   //输出路径

        if (car == 0){  //按不同交通方式找到不同路径进行模拟

            if (flag == 0) dijkstra.Simulation(42, end);
            else dijkstra.Simulation(26, end);
        }
        else{

            if (flag == 0) dijkstra.Simulation(43, end);
            else dijkstra.Simulation(33, end);
        }
    }

    public static void nearBy() throws IOException {    //周边导航方法

        Iterator iter = dijkstra.disMap.entrySet().iterator();

        int k = 0;  //当前找到的建筑数目

        while (iter.hasNext()) {    //寻找最近的10个非路口建筑(disMap排序的重要性体现)

            Map.Entry entry = (Map.Entry) iter.next();
            int key = (int)entry.getKey();

            if (!Input.buildings.get(key).Building_Name.equals("路口")) {
                k++;
                Navigation.resultList.add(Input.buildings.get(key));
            }

            if (k == 11) break;
        }

        for (int i = 1; i < Navigation.resultList.size(); i++){

            fileOutput.Cache(i + ":" + Navigation.resultList.get(i).Building_Name); //输出建筑列表

            if (Navigation.resultList.get(i).Devices.length != 0){      //输出建筑时输出其中的前5个设施(如果有5个),方便查看

                fileOutput.Cache(" 包括设施:");
                for (int j = 0; j < Math.min(5, Navigation.resultList.get(i).Devices.length); j++)
                    fileOutput.Cache(" " + Navigation.resultList.get(i).Devices[j]);

                if (Navigation.resultList.get(i).Devices.length > 5)    //设施数大于5,输出"等"
                    fileOutput.Cache("等");

                if (Navigation.mode != 1) fileOutput.Cache("  距离为：" + disMap.get(Navigation.resultList.get(i).ID) + "m");
                System.out.println();
            }else System.out.println();

        }
    }

    public static void output(int start, int end) throws IOException {  //控制输出start与end间的信息或模拟导航

        if ((start <= 41) && (end > 41)) {
            dijkstra.TP(start, 0, end);
        } else if ((end <= 41) && (start > 41)) {
            dijkstra.TP(start, 1, end);
        } else {

            if (dijkstra.disMap.get(end) > 100000) {
                fileOutput.Cacheln(true, "无法到达！");
                return;
            }
            dijkstra.outPutPath(end);
            dijkstra.Simulation(start, end);
        }
    }

    public static int course() throws IOException { //按课程表导航方法

        Scanner in = new Scanner(System.in);
        Calendar c = Calendar.getInstance();
        int tempWeek;

//        tempWeek = c.get(Calendar.DAY_OF_WEEK) - 1;
//        fileOutput.Cacheln(true, "今天是周" + tempWeek); //提供实时判断当前时周几的功能

        fileOutput.Cacheln(true, "今天是周几？(数入阿拉伯数字！！！例如:1 代表周一)");
        tempWeek = in.nextInt();

        fileOutput.Cacheln(false, tempWeek);

        while (tempWeek < 1 || tempWeek > 7){
            fileOutput.Cacheln(true, "输入错误！");
            fileOutput.Cacheln(true, "今天是周几？(数入阿拉伯数字！！！例如:1 代表周一)");
            tempWeek = in.nextInt();
            fileOutput.Cacheln(false, tempWeek);
        }

        fileOutput.Cacheln(true, "现在的时间为" + c.get(Calendar.HOUR_OF_DAY) + ":" + c.get(Calendar.MINUTE) + ":" + c.get(Calendar.SECOND));
        //int seconds = c.get(Calendar.HOUR_OF_DAY) * 3600 + c.get(Calendar.MINUTE) * 60 + c.get(Calendar.SECOND);  //提供实时功能
        int seconds = 39600;    //锁定为11:00

        for (course a:Input.coursesTable)

            if ((a.week == tempWeek) && ((a.hour * 3600 + a.min * 600) >= seconds)){    //寻找今天的在当前时间之后的课
                fileOutput.Cacheln(true, "下一节课：" + a.name + ", " + a.hour + ":" + a.min + "0," + " 在教室" + a.room); //输出信息
                return a.where; //返回所在建筑物的ID,作为主方法中的终点进行后续操作
            }

        fileOutput.Cacheln(true, "没有课啦！滚去图书馆学习！");    //如果没有课了,就去图书馆自习,也可以读入其他终点(修改return的内容即可)

        return 18;
    }

    public static void multiplePath(int start, int end) throws IOException {
        Scanner in = new Scanner(System.in);
        ArrayList<Integer> road = new ArrayList<>();
        int num;
        road.add(start);
        fileOutput.Cacheln(true, "输入途经点个数：");
        int tempNum = in.nextInt();
        fileOutput.Cacheln(false, tempNum);
        num = tempNum + 2;
        int[][] roadMap = new int[num][num];
        int[][] dp = new int[num - 1][1 << (num - 2)];
        ArrayList<Integer>[][] bestPath = new ArrayList[num - 1][1 << (num - 2)];

        for (int j = 0; j < num - 1; j++)
            for (int i = 0; i < 1 << (num - 2); i++)
                bestPath[j][i] = new ArrayList<>();

        for (int i = 0; i < tempNum; i++){
            Navigation.resultList.clear();
            while (Navigation.resultList.isEmpty()) {
                fileOutput.Cacheln(true, "输入途经点" + (i + 1));
                Search.getStart_End();
            }
            int index = in.nextInt();
            while (index < 0 || index >= Navigation.resultList.size()){
                fileOutput.Cacheln(true, "输入错误！请重新输入");
                index = in.nextInt();
            }
            road.add(Navigation.resultList.get(index).ID);
            fileOutput.Cacheln(false, index);
        }
        road.add(end);

        for (int i = 0; i < num - 1; i++){
            Dijkstra(road.get(i));
            roadMap[i][i] = 0;
            for (int j = i + 1; j < num; j++){
                roadMap[i][j] = disMap.get(road.get(j));
                roadMap[j][i] = disMap.get(road.get(j));
            }
        }

        for (int i = 0; i < num - 1; i++){
            dp[i][0] = roadMap[i][num - 1];
            bestPath[i][0].add(road.get(i));
        }

        for (int j = 1; j < (1 << (num - 2)); j++)
            for (int i = 0; i < num - 1; i++){
                dp[i][j] = 100000;

                if (((j >> (i - 1) & 1) == 1)) continue;

                for (int k = 1; k < num - 1; k++)
                    if (((j >> (k - 1)) & 1) == 1)
                        if (dp[i][j] > (roadMap[i][k] + dp[k][j ^ (1 << (k - 1))])) {
                            dp[i][j] = (roadMap[i][k] + dp[k][j ^ (1 << (k - 1))]);
                            bestPath[i][j].clear();
                            bestPath[i][j].add(road.get(i));
                            bestPath[i][j].addAll(bestPath[k][j ^ (1 << (k - 1))]);
                        }
            }

        if (dp[0][(1 << (num - 2)) - 1] == 100000) {
            fileOutput.Cacheln(true, "自行车无法走通该路径！");
            Navigation.curBuilding = Input.buildings.get(start);
            return;
        }

        bestPath[0][(1 << (num - 2)) - 1].add(end);

        ArrayList<Integer> nbPath = bestPath[0][(1 << (num - 2)) - 1];
        fileOutput.Cacheln(true, "推荐路径：");
        for (int i = 0; i < num; i++)
            fileOutput.Cache(Input.buildings.get(nbPath.get(i)).Building_Name + " ");
        if (Navigation.mode != 1) fileOutput.Cache("全程总距离为" + dp[0][(1 << (num - 2)) - 1] + "m\n");

        for (int i = 0; i < num - 1; i++){
            Dijkstra(nbPath.get(i));
            output(nbPath.get(i), nbPath.get(i + 1));
            if (stopFlag) break;
        }
    }
}